{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Average Subtree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumAverageSubtree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子树的最大平均值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树的根节点&nbsp;<code>root</code>，找出这棵树的 <strong>每一棵</strong> 子树的 <strong>平均值</strong> 中的 <strong>最大</strong> 值。</p>\n",
    "\n",
    "<p>子树是树中的任意节点和它的所有后代构成的集合。</p>\n",
    "\n",
    "<p>树的平均值是树中节点值的总和除以节点数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/07/12/1308_example_1.png\" style=\"height: 123px; width: 132px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[5,6,1]\n",
    "<strong>输出：</strong>6.00000\n",
    "<strong>解释： </strong>\n",
    "以 value = 5 的节点作为子树的根节点，得到的平均值为 (5 + 6 + 1) / 3 = 4。\n",
    "以 value = 6 的节点作为子树的根节点，得到的平均值为 6 / 1 = 6。\n",
    "以 value = 1 的节点作为子树的根节点，得到的平均值为 1 / 1 = 1。\n",
    "所以答案取最大值 6。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>树中的节点数介于&nbsp;<code>1</code> 到&nbsp;<code>5000</code>之间。</li>\n",
    "\t<li>每个节点的值介于&nbsp;<code>0</code> 到&nbsp;<code>100000</code>&nbsp;之间。</li>\n",
    "\t<li>如果结果与标准答案的误差不超过&nbsp;<code>10^-5</code>，那么该结果将被视为正确答案。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-average-subtree](https://leetcode.cn/problems/maximum-average-subtree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-average-subtree](https://leetcode.cn/problems/maximum-average-subtree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,6,1]', '[0,null,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        ans=0\n",
    "        def helper(node):\n",
    "            if not node:\n",
    "                return 0,0\n",
    "            lc,lv=helper(node.left)\n",
    "            rc,rv=helper(node.right)\n",
    "            nonlocal ans\n",
    "            ans=max(ans,(lv+rv+node.val)/(lc+rc+1))\n",
    "            return lc+rc+1,lv+rv+node.val\n",
    "        helper(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self._result = 0\n",
    "\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        return self.answer_1(root)\n",
    "\n",
    "    def answer_1(self, root):\n",
    "        self._dfs_1(root)\n",
    "        return self._result\n",
    "\n",
    "    def _dfs_1(self, node):\n",
    "        if not node:\n",
    "            return 0, 0\n",
    "\n",
    "        left_sum, left_cnt = self._dfs_1(node.left)\n",
    "        right_sum, right_cnt = self._dfs_1(node.right)\n",
    "\n",
    "        current_sum = left_sum + right_sum + node.val\n",
    "        current_cnt = left_cnt + right_cnt + 1\n",
    "\n",
    "        avg_num = current_sum / current_cnt\n",
    "        self._result = max(self._result, avg_num)\n",
    "        return current_sum, current_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "\n",
    "        def helper(node):\n",
    "            nonlocal max_aver\n",
    "            if not node:\n",
    "                return [0,0]\n",
    "            left = helper(node.left)\n",
    "            right = helper(node.right)\n",
    "            cur_sum = node.val+left[0]+right[0]\n",
    "            cur_div = 1+left[1]+right[1]\n",
    "            max_aver = max(max_aver,cur_sum/cur_div)\n",
    "            return [cur_sum,cur_div]\n",
    "        \n",
    "        max_aver = 0\n",
    "        helper(root)\n",
    "        return max_aver"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        self.max_avg = -float('inf')\n",
    "        self.result_node = None\n",
    "        def dfs(node):\n",
    "            if not node: \n",
    "                return (0, 0)\n",
    "            left_sum, left_num = dfs(node.left)\n",
    "            right_sum, right_num = dfs(node.right)\n",
    "            total_sum = left_sum + right_sum + node.val\n",
    "            total_num = left_num + right_num + 1\n",
    "            avg = total_sum / total_num\n",
    "            if avg > self.max_avg:\n",
    "                self.max_avg = avg\n",
    "                self.result_node = node\n",
    "            return (total_sum, total_num)\n",
    "\n",
    "        dfs(root)\n",
    "        return round(self.max_avg, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, node: Optional[TreeNode]) -> float:\n",
    "        ans = float('-inf')\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            left_sum, left_count = dfs(node.left)\n",
    "            right_sum, right_count = dfs(node.right)\n",
    "\n",
    "            current_sum = left_sum + right_sum + node.val\n",
    "            current_count = left_count + right_count + 1\n",
    "            ans = max(ans, current_sum/current_count)\n",
    "            return current_sum, current_count\n",
    "        dfs(node)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # Return (count, value)\n",
    "    def _maximumAverageSubtree(self, root):\n",
    "        if not root:\n",
    "            return (0, 0)\n",
    "\n",
    "        leftCnt, leftVal = self._maximumAverageSubtree(root.left)\n",
    "        rightCnt, rightVal = self._maximumAverageSubtree(root.right)\n",
    "\n",
    "        cnt = 1 + leftCnt + rightCnt\n",
    "        val = root.val + leftVal + rightVal\n",
    "        self.res = max(self.res, val / cnt)\n",
    "\n",
    "        return (cnt, val)\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        self.res = float('-inf')\n",
    "        self._maximumAverageSubtree(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        \n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            left_sum, left_count = dfs(node.left)\n",
    "            right_sum, right_count = dfs(node.right)\n",
    "            cur_sum = left_sum + right_sum + node.val\n",
    "            cur_count = left_count + right_count + 1\n",
    "            ans = max(ans, cur_sum / cur_count)\n",
    "            return cur_sum, cur_count\n",
    "        ans = 0\n",
    "        dfs(root)\n",
    "    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        def calc(root: Optional[TreeNode]) -> list[int,int]:\n",
    "            nonlocal res\n",
    "            if not root: return [0,0]\n",
    "            num,val = 1,root.val\n",
    "            if root.left: \n",
    "                left = calc(root.left)\n",
    "                num+=left[0]\n",
    "                val+=left[1]\n",
    "            if root.right:\n",
    "                right = calc(root.right)\n",
    "                num+=right[0]\n",
    "                val+=right[1]\n",
    "            res = max(res,val/num)\n",
    "            return num,val\n",
    "        res = 0.0\n",
    "        calc(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        self.res = 0\n",
    "        def find(pos):\n",
    "            if not pos:\n",
    "                return (0, 0)\n",
    "            SUM, COUNT = pos.val, 1\n",
    "            ltmp, rtmp = find(pos.left), find(pos.right)\n",
    "            SUM += ltmp[0]+rtmp[0]\n",
    "            COUNT += ltmp[1]+rtmp[1]\n",
    "            self.res = max(self.res, SUM/COUNT)\n",
    "            return (SUM, COUNT)\n",
    "        find(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        ans = float('-inf')\n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return 0,0\n",
    "            l, l_cnt = dfs(root.left)\n",
    "            r, r_cnt = dfs(root.right)\n",
    "\n",
    "            curr = l + r + root.val\n",
    "            curr_cnt = l_cnt + r_cnt + 1\n",
    "\n",
    "            ans = max(ans, curr/curr_cnt)\n",
    "            return curr, curr_cnt\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        self.ret = 0\n",
    "\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            left_avg, left_num = helper(root.left)\n",
    "            right_avg, right_num = helper(root.right)\n",
    "            sum_ = left_avg * left_num + right_avg * right_num + root.val\n",
    "            node_num = left_num + right_num + 1\n",
    "            self.ret = max(sum_ / node_num, self.ret)\n",
    "            return sum_ / node_num, node_num\n",
    "        helper(root)\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        ans=0\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            if x is None:\n",
    "                return 0,0\n",
    "            l_sum,l_cnt=dfs(x.left)\n",
    "            r_sum,r_cnt=dfs(x.right)\n",
    "            cur_sum=l_sum+r_sum+x.val\n",
    "            cur_cnt=l_cnt+r_cnt+1\n",
    "            ans=max(ans,cur_sum/cur_cnt)\n",
    "            return cur_sum,cur_cnt\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        result = 0\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                ls, ln = dfs(node.left)\n",
    "                rs, rn = dfs(node.right)\n",
    "                s, n = node.val + ls + rs, ln + rn + 1\n",
    "                nonlocal result\n",
    "                result = max(result, s / n)\n",
    "                return s, n\n",
    "            return 0, 0\n",
    "        dfs(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        maxAve = 0\n",
    "        def traversal(node):\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            lsum, lcnt = traversal(node.left)\n",
    "            rsum, rcnt = traversal(node.right)\n",
    "            isum = lsum + rsum + node.val\n",
    "            icnt = lcnt + rcnt + 1\n",
    "\n",
    "            nonlocal maxAve\n",
    "            maxAve = max(maxAve, isum / icnt)\n",
    "            \n",
    "            return isum, icnt\n",
    "        traversal(root)\n",
    "        return maxAve"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        if not root: return 0\n",
    "        ans = 0\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            if not root: return 0, 0\n",
    "            ls, ln = dfs(root.left)\n",
    "            rs, rn = dfs(root.right)\n",
    "            ans = max(ans, (root.val + ls + rs) / (ln + rn + 1))\n",
    "            return root.val + ls + rs, ln + rn + 1\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        res = -float(\"inf\")\n",
    "        def recur(root):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return 0,0\n",
    "            ls,ln = recur(root.left)\n",
    "            rs,rn = recur(root.right)\n",
    "            res = max(res,1.0*(ls+rs+root.val)/(ln+rn+1))\n",
    "            return ls+rs+root.val,ln+rn+1\n",
    "        recur(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        self.res = 0\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "    \n",
    "\n",
    "    def dfs(self, root):\n",
    "        if not root:\n",
    "            return 0, 0\n",
    "        left_sum, left_cnt = self.dfs(root.left)\n",
    "        right_sum, right_cnt = self.dfs(root.right)\n",
    "        total_sum = left_sum + right_sum + root.val\n",
    "        total_cnt = left_cnt + right_cnt + 1\n",
    "        self.res = max(self.res, total_sum / total_cnt)\n",
    "        return total_sum, total_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        res = -float(\"inf\")\n",
    "        def recur(root):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return 0,0\n",
    "            ls,ln = recur(root.left)\n",
    "            rs,rn = recur(root.right)\n",
    "            res = max(res,1.0*(ls+rs+root.val)/(ln+rn+1))\n",
    "            return ls+rs+root.val,ln+rn+1\n",
    "        recur(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root) -> float:\n",
    "        rootSum, maxAve_subtree, maxAve, treeNum = self.get_maxAve_subtree(root)\n",
    "        return maxAve\n",
    "    \n",
    "    def get_maxAve_subtree(self, root):\n",
    "        if not root:\n",
    "            return 0, None, -sys.maxsize-1, 0\n",
    "        left_rootSum, left_maxAve_subtree, left_maxAve, left_treeNum = self.get_maxAve_subtree(root.left)\n",
    "        right_rootSum, right_maxAve_subtree, right_maxAve, right_treeNum = self.get_maxAve_subtree(root.right)\n",
    "        \n",
    "        rootSum = (left_rootSum + right_rootSum + root.val)\n",
    "        treeNum = (left_treeNum + right_treeNum + 1)\n",
    "        rootAve = rootSum / treeNum\n",
    "        now_maxAve = max(left_maxAve, right_maxAve, rootAve)\n",
    "        if now_maxAve == left_maxAve:\n",
    "            return rootSum, left_maxAve_subtree, left_maxAve, treeNum\n",
    "        if now_maxAve == right_maxAve:\n",
    "            return rootSum, right_maxAve_subtree, right_maxAve, treeNum\n",
    "        return rootSum, root, rootAve, treeNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        ret = 0\n",
    "\n",
    "        def max_avg(node):\n",
    "            nonlocal ret\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "\n",
    "            sl, cl = max_avg(node.left)\n",
    "            sr, cr = max_avg(node.right)\n",
    "\n",
    "            s = (sl + sr + node.val) \n",
    "            c = (cl + cr + 1)\n",
    "            ret = max(ret, s / c)\n",
    "            return s, c\n",
    "\n",
    "        max_avg(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        max_num=float(\"-inf\")\n",
    "        def method(node):\n",
    "            nonlocal max_num\n",
    "            if node==None:\n",
    "                max_num=max(max_num,0)\n",
    "                return 0,0\n",
    "            else:\n",
    "                left_num,left_sum=method(node.left)\n",
    "                right_num,right_sum=method(node.right)\n",
    "\n",
    "                node_num=left_num+right_num+1\n",
    "                node_sum=left_sum+right_sum+node.val\n",
    "                max_num=max(max_num,node_sum/node_num)\n",
    "\n",
    "                return node_num,node_sum\n",
    "\n",
    "        method(root)\n",
    "        return max_num\n",
    "\n",
    "                \n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        self.maxAverage = 0\n",
    "        \n",
    "        def getAverage(node: Optional[TreeNode]) -> (float, int):\n",
    "            if node is None:\n",
    "                return (0, 0)\n",
    "\n",
    "            leftAv, leftNum = getAverage(node.left)\n",
    "            rightAv, rightNum = getAverage(node.right)\n",
    "            num = leftNum+rightNum+1\n",
    "            average = (leftAv*leftNum + rightAv*rightNum + node.val)/num\n",
    "            self.maxAverage = max(self.maxAverage, average)\n",
    "            return (average, num) \n",
    "        \n",
    "        \n",
    "        getAverage(root)\n",
    "        return self.maxAverage"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = float('-inf')\n",
    "\n",
    "    def dfsAverageSubtree(self, node: TreeNode) ->float:\n",
    "        if not node:\n",
    "            return 0, 0\n",
    "        leftSum, leftCount = self.dfsAverageSubtree(node.left)\n",
    "        rightSum, rightCount = self.dfsAverageSubtree(node.right)\n",
    "        curSum = leftSum + rightSum + node.val\n",
    "        curCount = leftCount + rightCount + 1\n",
    "        self.ans = max(self.ans, curSum/curCount)\n",
    "        return curSum, curCount             \n",
    "\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        self.dfsAverageSubtree(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        maxAve = 0\n",
    "        def traversal(node):\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            lsum, lcnt = traversal(node.left)\n",
    "            rsum, rcnt = traversal(node.right)\n",
    "            isum = lsum + rsum + node.val\n",
    "            icnt = lcnt + rcnt + 1\n",
    "\n",
    "            nonlocal maxAve\n",
    "            maxAve = max(maxAve, isum / icnt)\n",
    "            \n",
    "            return isum, icnt\n",
    "        traversal(root)\n",
    "        return maxAve"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        ans = -inf\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if node == None:\n",
    "                return 0, 0\n",
    "            left_cnt, left_sum = dfs(node.left)\n",
    "            right_cnt, right_sum = dfs(node.right)\n",
    "            cur_sum = left_sum + right_sum + node.val\n",
    "            cur_cnt = left_cnt + right_cnt + 1\n",
    "            ans = max(ans, cur_sum / cur_cnt)\n",
    "            return cur_cnt, cur_sum\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "      self.ret = -inf\n",
    "      def dfs(root: Optional[TreeNode]):\n",
    "        if not root:\n",
    "          return (0,0)\n",
    "        nodeCount = 1\n",
    "        nodeSum = root.val\n",
    "        (lNodeSum, lNodeCount),  (rNodeSum, rNodeCount)= dfs(root.left), dfs(root.right)\n",
    "        nodeCount+=lNodeCount+rNodeCount\n",
    "        nodeSum+=lNodeSum+rNodeSum\n",
    "        self.ret = max(self.ret, nodeSum/nodeCount)\n",
    "        return(nodeSum, nodeCount)\n",
    "      dfs(root)\n",
    "      return self.ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        self.ans = 0\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return (0, 0)\n",
    "            lt = dfs(root.left)\n",
    "            rt = dfs(root.right)\n",
    "            val = lt[0] + rt[0] + root.val\n",
    "            cnt = lt[1] + rt[1] + 1\n",
    "            avg = val / cnt\n",
    "            self.ans = max(avg, self.ans)\n",
    "            return (val, cnt)\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        # post binary tree iteration\n",
    "        def subtreeSum(root, maxAvg):\n",
    "            if root is None:\n",
    "                return 0, 0, 0\n",
    "            leftSum, leftCount, leftMaxAvg = subtreeSum(root.left, maxAvg)\n",
    "            rightSum, rightCount, rightMaxAvg = subtreeSum(root.right, maxAvg)\n",
    "            subSum = root.val + leftSum + rightSum\n",
    "            nodeCount = 1 + leftCount + rightCount\n",
    "            maxAvg = max(leftMaxAvg, rightMaxAvg, subSum / nodeCount)\n",
    "            return subSum, nodeCount, maxAvg\n",
    "        _, _, maxAvg = subtreeSum(root, 0)\n",
    "        return maxAvg\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            if not node:return 0,0\n",
    "            l, r = dfs(node.left), dfs(node.right)\n",
    "            Count, Num = 1, node.val\n",
    "            if l and  r and node:\n",
    "                Count = l[0] + r[0] + 1\n",
    "                Num = (node.val + l[0] * l[1] + r[0] * r[1])/Count\n",
    "            if not l and r and node:\n",
    "                Count = r[0] + 1\n",
    "                Num = (node.val + r[0] * r[1])/Count\n",
    "            if not r and l and node:\n",
    "                Count = l[0] + 1\n",
    "                Num = (node.val + l[0] * l[1])/Count\n",
    "            res = max(res, Num)\n",
    "            return Count, Num\n",
    "        res = 0\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        maxmean = 0\n",
    "        def dfs(root):\n",
    "            nonlocal maxmean\n",
    "            if not root:\n",
    "                return (0, 0)\n",
    "            left_sum, left_count = dfs(root.left)\n",
    "            right_sum, right_count = dfs(root.right)\n",
    "            cur_sum = left_sum + right_sum + root.val\n",
    "            cur_count = left_count + right_count + 1\n",
    "            mean = cur_sum / cur_count\n",
    "            maxmean = max(maxmean, mean)\n",
    "            return (cur_sum, cur_count)\n",
    "        \n",
    "        dfs(root)\n",
    "        return maxmean"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        self.res = 0 \n",
    "\n",
    "        self.subTreeSum(root)\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def subTreeSum(self, root):\n",
    "        if root is None:\n",
    "            return 0, 0\n",
    "\n",
    "        left_sum, left_node = self.subTreeSum(root.left)\n",
    "        right_sum, right_node = self.subTreeSum(root.right)\n",
    "\n",
    "        root_sum = root.val + left_sum + right_sum \n",
    "        cnt = 1 + left_node + right_node \n",
    "\n",
    "        self.res = max(self.res, root_sum / cnt)\n",
    "\n",
    "        return root_sum, cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        res = -float('inf')\n",
    "        def recur(root):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return 0,0\n",
    "            ls,ln = recur(root.left)\n",
    "            rs,rn = recur(root.right)\n",
    "            res = max(res,1.0*(ls+rs+root.val)/(ln+rn+1))\n",
    "            return ls+rs+root.val,ln+rn+1\n",
    "        recur(root) \n",
    "        return res\n",
    "        # res = -float(\"inf\")\n",
    "        # def recur(root):\n",
    "        #     nonlocal res\n",
    "        #     if not root:\n",
    "        #         return 0,0\n",
    "        #     ls,ln = recur(root.left)\n",
    "        #     rs,rn = recur(root.right)\n",
    "        #     res = max(res,1.0*(ls+rs+root.val)/(ln+rn+1))\n",
    "        #     return ls+rs+root.val,ln+rn+1\n",
    "        # recur(root)\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: TreeNode) -> float:\n",
    "        ans = float('-inf')\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            left_sum, left_count = dfs(node.left)\n",
    "            right_sum, right_count = dfs(node.right)\n",
    "            cur_sum = left_sum + right_sum + node.val\n",
    "            cur_count = left_count + right_count + 1\n",
    "            ans = max(ans, cur_sum / cur_count)\n",
    "            return cur_sum, cur_count\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 注意：python 代码由 chatGPT\\U0001f916 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。\n",
    "# 本代码已经通过力扣的测试用例，应该可直接成功提交。\n",
    "\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: TreeNode) -> float:\n",
    "        self.maxAvg = 0\n",
    "        self.getCountAndSum(root)\n",
    "        return self.maxAvg\n",
    "\n",
    "    # 定义：输入 root，返回以 root 为根的二叉树的节点个数和节点值之和\n",
    "    def getCountAndSum(self, root: TreeNode) -> List[int]:\n",
    "        if root is None:\n",
    "            return [0, 0]\n",
    "\n",
    "        # 先拿到左右子树的节点个数和节点之和\n",
    "        left = self.getCountAndSum(root.left)\n",
    "        right = self.getCountAndSum(root.right)\n",
    "\n",
    "        leftCount, leftSum = left[0], left[1]\n",
    "        rightCount, rightSum = right[0], right[1]\n",
    "\n",
    "        rootCount = leftCount + rightCount + 1\n",
    "        rootSum = root.val + leftSum + rightSum\n",
    "\n",
    "        # 后序位置，计算全局的最大平均值\n",
    "        self.maxAvg = max(self.maxAvg, 1.0 * rootSum / rootCount)\n",
    "\n",
    "        # 实现函数的定义\n",
    "        return [rootCount, rootSum]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        # 后序遍历，每个节点返回当前子树的个数和值的总和\n",
    "        # 并在当前节点计算最大平均值\n",
    "        if not root: return 0\n",
    "        self.ans = 0\n",
    "        self.traverse(root)\n",
    "        return self.ans\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root: return 0, 0\n",
    "        left_sum, left_num = self.traverse(root.left)\n",
    "        right_sum, right_num = self.traverse(root.right)\n",
    "\n",
    "        cur_mean = (left_sum+right_sum+root.val)/(left_num+right_num+1)\n",
    "        self.ans = max(self.ans, cur_mean)\n",
    "        return left_sum+right_sum+root.val, left_num+right_num+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        anw = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal anw\n",
    "            if not node:\n",
    "                return [0,0]\n",
    "            \n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "\n",
    "            left[0] = node.val + left[0] + right[0]\n",
    "            left[1] = 1 + left[1] + right[1]\n",
    "\n",
    "            anw = max(anw, left[0]/left[1])\n",
    "\n",
    "            return left\n",
    "        \n",
    "        dfs(root)\n",
    "        return anw"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: TreeNode) -> float:\n",
    "        ans = float('-inf')\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            left_sum, left_count = dfs(node.left)\n",
    "            right_sum, right_count = dfs(node.right)\n",
    "            cur_sum = left_sum + right_sum + node.val\n",
    "            cur_count = left_count + right_count + 1\n",
    "            ans = max(ans, cur_sum / cur_count)\n",
    "            return cur_sum, cur_count\n",
    "\n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        if not root: return 0\n",
    "        def dfs(root):\n",
    "            if not root: return 0,0\n",
    "            nonlocal res\n",
    "            leftcur, leftnum = dfs(root.left)\n",
    "            rightcur, rightnum = dfs(root.right)\n",
    "            cur = leftcur+rightcur+root.val\n",
    "            num =leftnum+rightnum+1\n",
    "            res = max(res,cur/num)\n",
    "            return cur, num\n",
    "        dfs(root)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "\n",
    "        self.max_avg = 0\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return (0, 0)\n",
    "            if not root.left and not root.right:\n",
    "                self.max_avg = max(self.max_avg, root.val)\n",
    "                return (root.val, 1)\n",
    "\n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "\n",
    "            total = l[0] + r[0] + root.val\n",
    "            count = l[1] + r[1] + 1\n",
    "            avg = total / count\n",
    "            \n",
    "            self.max_avg = max(self.max_avg, avg)\n",
    "\n",
    "            return (total, count)\n",
    "\n",
    "        dfs(root)\n",
    "        return self.max_avg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        ans = -float(inf)\n",
    "        def dfs(node):\n",
    "            nonlocal ans \n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            left_sum, left_count = dfs(node.left)\n",
    "            right_sum, right_count = dfs(node.right)\n",
    "            cur_sum = left_sum + right_sum + node.val \n",
    "            cur_count = left_count + right_count + 1\n",
    "            ans = max(ans, cur_sum / cur_count)\n",
    "            return cur_sum, cur_count\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Info:\n",
    "    def __init__(self, num = 0, avg = 0):\n",
    "        self.num = num\n",
    "        self.avg = avg\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        res = 0\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            if node is None:\n",
    "                return Info()\n",
    "            L_I, R_I = dfs(node.left), dfs(node.right)\n",
    "            L_sum = L_I.num * L_I.avg\n",
    "            R_sum = R_I.num * R_I.avg\n",
    "            num = L_I.num + R_I.num + 1\n",
    "            avg = (L_sum + R_sum + node.val) / num\n",
    "            if avg > res:\n",
    "                res = avg\n",
    "            return Info(num, avg)\n",
    "        dfs(root)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        def get_num_and_sum_of_subtree(root):\n",
    "            if not root:\n",
    "                return (0, 0, 0)\n",
    "\n",
    "            left_num, left_sum, left_max_avg = get_num_and_sum_of_subtree(root.left)\n",
    "            right_num, right_sum, right_max_avg = get_num_and_sum_of_subtree(root.right)\n",
    "\n",
    "            cur_num = left_num + right_num + 1\n",
    "            cur_sum = left_sum + right_sum + root.val\n",
    "            cur_avg = cur_sum / cur_num\n",
    "            cur_max_avg = max(cur_avg, left_max_avg, right_max_avg)\n",
    "\n",
    "            return (cur_num, cur_sum, cur_max_avg)\n",
    "        \n",
    "        return get_num_and_sum_of_subtree(root)[2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        maxavg = 0\n",
    "\n",
    "        def helper(node):\n",
    "            nonlocal maxavg\n",
    "            totalnode = 1\n",
    "            totalval = node.val\n",
    "            if node.left:\n",
    "                leftval = helper(node.left)\n",
    "                totalnode += leftval[0]\n",
    "                totalval += leftval[1]\n",
    "            if node.right:\n",
    "                rightval = helper(node.right)\n",
    "                totalnode += rightval[0]\n",
    "                totalval += rightval[1]\n",
    "            curavg = totalval / totalnode\n",
    "            if curavg > maxavg:\n",
    "                maxavg = curavg\n",
    "            return (totalnode, totalval)\n",
    "        helper(root)\n",
    "        return maxavg\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        \n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return 0, 0, 0\n",
    "\n",
    "            left_cnt, left_sum, left_ave = dfs(root.left)\n",
    "            right_cnt, right_sum, right_ave = dfs(root.right)\n",
    "\n",
    "            cnt = left_cnt + right_cnt + 1\n",
    "            all_sum = left_sum + right_sum + root.val\n",
    "            ave = max(left_ave, right_ave, all_sum / cnt)\n",
    "            \n",
    "            return cnt, all_sum, ave\n",
    "        \n",
    "        return dfs(root)[2]\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:\n",
    "        self.res = 0\n",
    "        def dfs(root):\n",
    "            # nonlocal maxval\n",
    "            if not root: return 0, 0\n",
    "            L_cnt, L_sum = dfs(root.left)  #左子树 结点个数 结点和\n",
    "            R_cnt, R_sum = dfs(root.right) #右子树 结点个数 结点和\n",
    "\n",
    "            cur_cnt = L_cnt+1+R_cnt  #当前树 结点总个数 结点总和\n",
    "            cur_sum = L_sum+root.val + R_sum  #当前树 结点总个数 结点总和\n",
    "\n",
    "            self.res = max(self.res, cur_sum/cur_cnt)\n",
    "            return cur_cnt,cur_sum\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
